package com.hdu.point_offer;

public class lcr183 {
    class Solution {
        int N = 10000;
        int[] Q = new int[N];
        int H = 0, T = 0;

        public int[] maxAltitude(int[] heights, int limit) {
            if (heights.length == 0)
                return new int[]{};
            refresh();
            int[] ans = new int[heights.length - limit + 1];
            for (int i = 0; i < limit; i++)
            {
                add(heights, i);
            }
            int index = 0;
            ans[index++] = max(heights);
            for (int i = limit; i < heights.length; i++)
            {
                delete(i - limit);
                add(heights, i);
                ans[index++] = max(heights);
            }
            return ans;
        }

        void refresh()
        {
            H = T = 0;
        }

        int max(int[] nums)
        {
            return nums[Q[H]];
        }

        void delete(int index)
        {
            if (Q[H] == index) H++;
        }

        void add(int[] nums, int index)
        {
            while (H < T && nums[index] >= nums[Q[T - 1]])
            {
                T--;
            }
            Q[T++] = index;
        }
    }
}
